package com.smh;

import com.smh.interfaces.Priority;
import com.smh.interfaces.Queue;
import org.junit.jupiter.api.Test;

/**
 * @author shiminghui
 * @date 2025/2/18 15:55
 * @description: TODO
 */
public class _026_优先级队列_二叉树 {


    @Test
    public void test1() {

        PriorityQueue<Entry<Integer>> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(new Entry<>(1, 1));
        priorityQueue.offer(new Entry<>(2, 2));
        priorityQueue.offer(new Entry<>(3, 3));
        priorityQueue.offer(new Entry<>(4, 4));
        priorityQueue.offer(new Entry<>(5, 5));
        Entry<Integer> poll = priorityQueue.poll();
        System.out.println(poll.value());
        priorityQueue.offer(new Entry<>(6, 1));
        poll = priorityQueue.poll();
        System.out.println(poll.value());
        poll = priorityQueue.poll();
        System.out.println(poll.value());
        poll = priorityQueue.poll();
        System.out.println(poll.value());
        poll = priorityQueue.poll();
        System.out.println(poll.value());
        poll = priorityQueue.poll();
        System.out.println(poll.value());


    }


    private static class PriorityQueue<T extends Priority> implements Queue<T> {

        private T[] array;
        private int size;
        private int capacity;

        @SuppressWarnings("unchecked")
        public PriorityQueue(int capacity) {
            this.capacity = capacity;
            array = (T[]) new Priority[capacity];
        }

        public PriorityQueue() {
            this(10);
        }

// 根据子节点找父节点 即子节点的索引-1 再除以2
        // 根据父节点找子节点 即父节点的索引*2+1 再+1 得到左右子节点

        @Override
        public boolean offer(T value) {
            if (isFull()) {
                return false;
            }
            int child = size;
            int parent = (child - 1) / 2;
            while (child > 0 && value.priority() > array[parent].priority()) {
                array[child] = array[parent];
                child = parent;
                parent = (child - 1) / 2;
            }
            array[child] = value;
            size++;
            return true;
        }

        @Override
        public T poll() {
            if (isEmpty()) {
                return null;
            }
            T t = array[0];
            T last = array[size - 1];
            array[0] = last;
            array[size - 1] = null;
            size--;
            // 调整堆
            int parent = 0;
            while (true) {
                int left = parent * 2 + 1;
                int right = left + 1;
                int max = parent;
                if (left < size && array[left].priority() > array[max].priority()) { // 左子节点大于父节点
                    max = left;
                }
                if (right < size && array[right].priority() > array[max].priority()) { // 右子节点大于左节点和父节点
                    max = right;
                }
                if (max == parent) {
                    array[parent] = last;
                    break;
                }
                array[parent] = array[max];
                array[max] = last;
                parent = max;
            }
            return t;
        }

        @Override
        public T peek() {
            if (isEmpty()) {
                return null;
            }
            return array[0];
        }

        @Override
        public boolean isEmpty() {
            return size == 0;
        }

        @Override
        public boolean isFull() {
            return size == capacity;
        }
    }

    private class Entry<T> implements Priority {
        private T value;
        private int priority;

        public Entry(T value, int priority) {
            this.value = value;
            this.priority = priority;
        }

        private Entry() {
        }

        public T value() {
            return value;
        }

        @Override
        public int priority() {
            return priority;
        }
    }

}
